package main

import (
	"fmt"
	"os"
)

/*
约瑟夫问题为：设编号1,2,...,n的n个人围坐一圈，约定编号为k(1<=k<=n)的人
从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又
出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列

提示：
用一个不带结点的循环链表来处理约瑟夫问题，先构成一个有n个结点的单循环链表，
然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除节点的
下一个结点又从1开始计数，直到最后一个结点从链表中删除结束
*/
//小孩的结构体
type Boy struct {
	no   int
	next *Boy //默认值是nil
}

//编写一个函数，构成单向的环形链表
//num：表示小孩的个数
//*Boy：返回该环形的链表的第一个小孩的指针
func AddBoy(num int) *Boy {
	first := &Boy{} //空节点
	curBoy := &Boy{}
	//判断
	if num < 1 {
		fmt.Println("num的值不对")
		return first
	}
	//循环构建这个环形链表
	for i := 1; i <= num; i++ {
		boy := &Boy{
			no: i,
		}
		//分析构成循环链表，需要一个辅助指针
		//1因为第一个小孩比较特殊
		if i == 1 { //第一个小孩
			first = boy
			curBoy = boy
			curBoy.next = first
		} else {
			curBoy.next = boy
			curBoy = boy
			curBoy.next = first //构成环形链表
		}
	}
	return first
}

//显示单向环形链表
func ShowBoy(first *Boy) {
	//处理一下如果环形链表为空
	if first.next == nil {
		fmt.Println("链表为空，没有小孩...")
		return
	}
	//创建一个指针，帮助遍历
	curBoy := first
	for {
		fmt.Printf("小孩编号=%d ->", curBoy.no)
		//退出条件
		if curBoy.next == first {
			break
		}
		//curBoy移动到下一个
		curBoy = curBoy.next
	}
	fmt.Println()
}

//分析思路
//1编写一个函数
//2最后使用一个算法，按照要求，在环形链表中留下最后一个人
func PlayGame(first *Boy, startNo int, countNum int) {
	//1空的链表单独处理
	if first.next == nil {
		fmt.Println("空链表")
		return
	}
	//留一个，判断startNo<=小孩的总数
	//2需要定义一个辅助指针，帮助删除小孩
	tail := first
	//3让tail指向环形链表的最后一个小孩，非常重要
	//因为tail在删除小孩时需要用到
	for {
		if tail.next == first { //说明tail到了最后的小孩
			break
		}
		tail = tail.next
	}
	//4让first移动到startNo [后面删除小孩，就以first为准]
	for i := 1; i <= startNo-1; i++ {
		first = first.next
		tail = tail.next
	}
	//5开始数countNum，然后就删除first指向的小孩
	for {
		//开始数countNum-1次
		for i := 1; i <= countNum-1; i++ {
			first = first.next
			tail = tail.next
		}
		fmt.Printf("小孩的编号为%d 出圈\n", first.no)
		//删除first指向的小孩
		first = first.next
		tail.next = first
		//判断如果tail==first，说明圈子中只有一个小孩
		if tail == first {
			break
		}
	}
	//最后一个小孩出圈
	fmt.Printf("小孩的编号为%d 出圈\n", first.no)
}
func main() {
	var boyNum int
	var startNo int
	var countNum int
	var key string
	first := &Boy{}
	for {
		fmt.Println("1输入add表示参与人数")
		fmt.Println("2输入km表示从编号startNo还是数数和数到countNum的小孩出列")
		fmt.Println("3输入exit退出")
		fmt.Scanln(&key)
		switch key {
		case "add":
			fmt.Println("输入参与人数：")
			fmt.Scanln(&boyNum)
			first = AddBoy(boyNum)
			ShowBoy(first)
		case "km":
			fmt.Println("输入编号：")
			fmt.Scanln(&startNo)
			fmt.Println("输入数多少下：")
			fmt.Scanln(&countNum)
			fmt.Println("出圈情况如下：")
			PlayGame(first, startNo, countNum)
		case "exit":
			os.Exit(0)
		}
	}
}
